package october;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Set;

public class GraphProblems {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.addEdge(n2, 2);
        n2.addEdge(n3, 3);
        n3.addEdge(n1, 9);

        int n = 3;
        final int[] d = new int[n];
        for (int i = 0; i < n; i++) d[i] = Integer.MAX_VALUE;
        d[0] = 0;
        PriorityQueue<Node> nodesToVisit = new PriorityQueue<Node>(n, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return d[o1.data - 1] - d[o2.data - 1];
            }
        });
        nodesToVisit.add(n1);
        while (!nodesToVisit.isEmpty()) {
            Node current = nodesToVisit.poll();
            if (current.edges != null) {
                for (Edge e : current.edges) {
                    Node target = e.trg;
                    int distanceThrough = d[current.data - 1] + e.weight;
                    if (d[e.trg.data - 1] > distanceThrough) {
                        nodesToVisit.remove(target);
                        d[e.trg.data-1] = distanceThrough;
                        nodesToVisit.add(target);
                    }
                }
            }
        }

    }

    private static class Edge {
        Node src, trg;
        int weight;

        private Edge(Node src, Node trg, int weight) {
            this.src = src;
            this.trg = trg;
            this.weight = weight;
        }
    }

    private static class Node {
        int data;
        Set<Edge> edges;

        private Node(int data, Set<Edge> edges) {
            this.data = data;
            this.edges = edges;
        }

        private Node(int data) {
            this.data = data;
        }

        private void addEdge(Node target, int weight) {
            this.edges.add(new Edge(this, target, weight));
        }
    }
}
